package mianshi;

public class CollectionText {
    /*
        ArrayList
            底层是数组，1.5倍扩容，线程不安全，默认容量是10，线程不安全
            查询快，因为底层是数组，可以通过索引查询
            增删慢，每次删除元素时都要将后面的元素向前移动

        ArrayList为什么线程不安全?
            会产生数据被覆盖的情况
            elementData[size++] = e;
            size++是非原子性操作,会存在线程安全问题,从而导致并发环境下数据被覆盖

        Vector
        线程安全的ArrayList,每个方法都采用synchronized修饰，因此是线程安全的
        2倍扩容

        LinkedList
        底层是一个双向链表，线程不安全
        增删快，因为底层是双向链表，删除时只需要将上一个节点的指针指向下一个节点即可完成删除操作
        查询慢，查询时，每次都要遍历一半的链表

        LinkedList为什么线程不安全?
            并发的情况下,会导致这样的问题
                                node1
                                /  \
                            node2   node3



        HashSet
            底层是HashMap,保存的是HashMap的key,key不能重复


        TreeSet


        LinkHashSet
            底层是LinkedHashMap

        HashMap
            可以存储null键和null值
            put流程:
                先通过哈希算法计算key的哈希值,通过哈希值与数组的长度计算出该key存储的哈希桶位置,
                然后查看哈希桶已经存在节点,如果不存在则直接插入节点,如果存在则通过头插法或者尾插法再插入节点
                插入节点之后, 如果节点数量大于等于8, 则单链表会转换成红黑树. 之后,会再判断是否需要扩容
            扩容流程:
                当元素数量达到阈值时,阈值=负载因子(默认0.75)*数组长度, 会进行扩容操作,容量扩大到原来的两倍,
                为什么会扩大两倍? 一个是为了让元素尽量分散,减少哈希碰撞的次数,二是减小链表的长度,从而加快查找的速度
                扩容成为原先的两倍之后,会再计算各个元素的哈希桶的位置,一部分元素还是保存在原来的哈希桶,而另一部分则
                会保存在oldCap+index的位置,即原来的索引+原来的数组长度,从而减小了链表的长度

            get流程:
                计算出key的哈希值,计算出哈希桶的位置,再遍历链表查找是否存在相同的key值,存在则返回对应的value值

            remove流程:
                先执行一遍get流程,判断要删除的元素是否存在,存在则删除对应的节点,如果是红黑树,
                则再判断当前哈希桶的节点的数量是否小于等于6,如果小于等于6,则将红黑树转换成单链表

            从各个流程来看,HashMap中最重要的就是哈希算法,哈希算法不仅要保证效率,还要减小发生哈希碰撞的次数

        HashMap为什么线程不安全?

            在JDK7中,因为采用的是头插法,在并发的环境下, 扩容的时候会产生循环链表,
                循环链表会导致HashMap执行get操作查询时产生死循环


            在JDK8中, 虽然采用的尾插法不会产生循环链表的问题,但是在并发的环境下,可能会产生数据覆盖的情况.
                比如在哈希桶为空时,有两个节点同时插入该哈希桶,因为已经计算过哈希桶的位置,第一个节点插入成功了,
                第二个节点再插入时,就会将第一个节点给覆盖掉.而在ConcurrentHashMap中,则采用CAS算法无锁插入首个节点,
                保证了插入首节点的线程安全问题.
                还有就是即使不是首节点,当有多个节点同时插入同一个哈希桶时,也可能会产生
                                                node1
                                                /  \
                                            node2   node3
                 的情况,而在ConcurrentHashMap中,则是在产生哈希碰撞的情况下,用synchronized锁住头结点,
                 保证了同一时间只有一个线程能添加节点,从而保证了线程安全


       HashMap中JDK7和JDK8的区别

        JDK7 :
            数组+链表 ，头插法，在并发的情况下可能会产生循环链表，循环链表会导致查询的时候出现死循环
            调用构造函数初始化时,就会立即创建一个容量为16的HashMap
        JDK8：
            数组+链表+红黑树，尾插法
            懒加载,第一次执行put方法添加数据时才会初始化容量为16(默认)的容器


        TreeMap


        LinkedHashMap


        ConcurrentHashMap
            不可以存储null键和null值
        JDK7:
            头插法
            Segment分段锁 + ReentrantLock : 锁的粒度为Segment的大小

        JDK8:
            尾插法
            CAS + synchronized :锁粒度为每个哈希桶, 锁住每个哈希桶的头结点,

        ConcurrentHashMap在JDK8之后为什么不用ReentrantLock而采用synchronized ?
            即ReentrantLock和synchronized的区别

请注意Synchronized上锁的对象,请记住,Synchronized是靠对象的对象头和此对象对应的monitor来保证上锁的,
也就是对象头里的重量级锁标志指向了monitor,而monitor呢,内部则保存了一个当前线程,也就是抢到了锁的线程.
那么这里的这个f是什么呢?它是Node链表里的每一个Node,也就是说,Synchronized是将每一个Node对象作为了一个锁,
这样做的好处是什么呢?将锁细化了,也就是说,除非两个线程同时操作一个Node,注意,是一个Node而不是一个Node链表哦,那么才会争抢同一把锁.
如果使用ReentrantLock其实也可以将锁细化成这样的,只要让Node类继承ReentrantLock就行了,这样的话调用f.lock()
就能做到和Synchronized(f)同样的效果,但为什么不这样做呢?
请大家试想一下,锁已经被细化到这种程度了,那么出现并发争抢的可能性还高吗?还有就是,哪怕出现争抢了,只要线程可以
在30到50次自旋里拿到锁,那么Synchronized就不会升级为重量级锁,而等待的线程也就不用被挂起,我们也就少了挂起和唤醒这个上下文切换的过程开销.
但如果是ReentrantLock呢?它则只有在线程没有抢到锁,然后新建Node节点后再尝试一次而已,不会自旋,而是直接被挂起,这样一来,
我们就很容易会多出线程上下文开销的代价.当然,你也可以使用tryLock(),但是这样又出现了一个问题,你怎么知道tryLock的时间呢?
在时间范围里还好,假如超过了呢?
所以,在锁被细化到如此程度上,使用Synchronized是最好的选择了.这里再补充一句,Synchronized和ReentrantLock他们的开销差距是
在释放锁时唤醒线程的数量,Synchronized是唤醒锁池里所有的线程+刚好来访问的线程,而ReentrantLock则是当前线程后进来的第一个
线程+刚好来访问的线程.
如果是线程并发量不大的情况下,那么Synchronized因为自旋锁,偏向锁,轻量级锁的原因,不用将等待线程挂起,偏向锁甚至不用自旋,
所以在这种情况下要比ReentrantLock高效

        HashTable
            不可以存储null键和null值
            同步的HashMap
            每个方法都用synchronized修饰来保证线程安全

     */
}
